package leetcode.dp;

public class MinimumPathSum64 {
    public static void main(String[] args) {
        new MinimumPathSum64().new Solution3().minPathSum(new int[][]{
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        });

    }
    class Solution1 {
        public int minPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            dp[0][0] = grid[0][0];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != 0 && j != 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                    } else if (i != 0) {
                        dp[i][j] = dp[i - 1][j] + grid[i][j];
                    }  else if (j != 0) {
                        dp[i][j] = dp[i][j - 1] + grid[i][j];
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    }

    class Solution2 {
        public int minPathSum(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
                return 0;
            }
            int m = grid.length;
            int n = grid[0].length;
            int[] dp = new int[n];
            dp[0] = grid[0][0];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i != 0 && j != 0) {
                        dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                    } else if (i != 0) {
                        dp[j] += grid[i][j];
                    }  else if (j != 0) {
                        dp[j] = dp[j - 1] + grid[i][j];
                    }
                }
            }
            return dp[n - 1];
        }
    }

    //打印路径
    class Solution3 {
        int m, n;
        public int minPathSum(int[][] grid) {
            m = grid.length;
            n = grid[0].length;
            int[][] dp = new int[m][n];
            int[] g = new int[m * n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0 && j == 0) {
                        dp[i][j] = grid[i][j];
                    } else {
                        int top  = i - 1 >= 0 ? dp[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
                        int left = j - 1 >= 0 ? dp[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                        dp[i][j] = Math.min(top, left);
                        g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1);
                    }
                }
            }

            // 从「结尾」开始，在 g[] 数组中找「上一步」
            int idx = getIdx(m - 1, n - 1);
            // 逆序将路径点添加到 path 数组中
            int[][] path = new int[m + n][2];
            path[m + n - 1] = new int[]{m - 1, n - 1};
            for (int i = 1; i < m + n; i++) {
                path[m + n - 1 - i] = parseIdx(g[idx]);
                idx = g[idx];
            }
            // 顺序输出位置
            for (int i = 1; i < m + n; i++) {
                int x = path[i][0], y = path[i][1];
                System.out.print("(" + x + "," + y + ") ");
            }
            System.out.println(" ");

            return dp[m - 1][n - 1];
        }
        int[] parseIdx(int idx) {
            return new int[]{idx / n, idx % n};
        }
        int getIdx(int x, int y) {
            return x * n + y;
        }
    }
}
